/*
	c++大二下学期实验一：递归与分治策略应用基础
	实验要求：
		1.认真领会分治法、递归技术方法提要,练习利用分治法分析问题、解决问程序,加深对它的理解
		2.阅读经典问题关键代码段,仔细领会算法、代码的异同。 
		3. 选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。
		4. 实验要有详细的测试记录，包括各种可能的测试数据。
	选择问题： 最大子段和 
*/
#include<bits/stdc++.h>
using namespace std;
class Max_find{
	private:
		vector<int> data;//字段存储 
		int data_length=0;//字段长度 
	public:
		int set_data(int length){
			int i;
			char mid;
			if(length <= 0){
				return -1;
			}
			srand((int)time(0));
			for(i=0;i<length;i++){
				data.push_back(rand()%(201)-100);
			}
			data_length=length;
			return 0;
		}
		void show_data(){
			int i;
			if(data_length==0){
				cout << "数组为空！" << endl;
			}else{
				cout << "data_length(" << data_length << "): ";
				for(i=0;i<data_length;i++){
					cout << data[i] <<" ";
				}
				cout << endl;
			}
		}
		void cut_data(){
			vector<int>().swap(data);
			data_length=data.size();
			cout << "删除完成!" << endl;
		}
		int maxsum(int left, int right)
			{
			    int sum=0;
			    int center,leftsum,rightsum,s1,lefts,i,s2,rights,j;
			    if (left==right)        //如果序列长度为1，直接求解
			    {
			        if (data[left]>0)
			            sum=data[left];
			        else
			            sum=0;
			    }
			    else
			    {
			        center=(left+right)/2;    //划分
			        leftsum=maxsum(left, center);
			        //对应情况①，递归求解
			        rightsum=maxsum(center+1, right);
			        //对应情况②，递归求解
			        s1=0;
			        lefts=0;
			//以下对应情况③，先求解s1
			        for (i=center; i>=left; i--)
			        {
			            lefts+=data[i];
			            if (lefts>s1)
			                s1=lefts;
			        }
			        s2=0;
			        rights=0;             //再求解s2
			        for (j=center+1; j<=right; j++)
			        {
			            rights+=data[j];
			            if (rights>s2)
			                s2=rights;
			        }
			        sum=s1+s2;              //计算情况③的最大子段和
			        if (sum<leftsum)
			            sum=leftsum;
			        //合并，在sum、leftsum和rightsum中取较大者
			        if (sum<rightsum)
			            sum=rightsum;
			    }
			    return sum;
			}
		int get_length(){
			return data_length;
		}
};
int main(){
	Max_find f1;
	f1.set_data(10);
	f1.show_data();
	cout << f1.maxsum(0, f1.get_length()-1) << endl;
	f1.cut_data();
	return 0;
} 
